package com.java.sort;

import java.util.Arrays;
import java.util.Random;

/**
 * 归并排序
 * @author 19252
 * @date 2020/7/19
 */
public class MergeSort {

    public static void main(String[] args) {
        MergeSort mergeSort = new MergeSort();
        int[] array = new int[]{-9, 78, 0, 23, -567, 70, -1, 900, 4561};
        int[] temp = new int[array.length];
        mergeSort.disintegrateAndMergeSort(array, 0, array.length - 1, temp);
        System.out.println(Arrays.toString(array));

        // 效率测试
        Random random = new Random();
        int[] testArray = new int[8000000];
        for (int i = 0; i < 8000000; i++) {
            testArray[i] = random.nextInt(8000000);
        }

        long millis = System.currentTimeMillis();
        mergeSort.disintegrateAndMergeSort(testArray, 0, testArray.length - 1, new int[testArray.length]);
        millis = System.currentTimeMillis() - millis;
        System.out.println("数据排序所需的时间：" + millis + "毫秒");
    }

    /**
     * 归并排序
     * disintegrate 分解
     * Merge 合并
     * @param array 需要排序的数组
     * @param left 需要排序的数组的初始索引
     * @param right 需要排序的数组的最后索引
     * @param temp 保存分组数组的中间数组
     */
    public void disintegrateAndMergeSort(int[] array, int left, int right, int[] temp){
        // 数组分组的中间节点
        int mid;
        if (left < right){
            mid = (left + right) / 2;

            // 向左递归进行分解
            // 最后只有一个元素不能再分解
            disintegrateAndMergeSort(array, left, mid, temp);

            // 向右递归进行分解
            // 最后只有一个元素不能再分解
            disintegrateAndMergeSort(array, mid + 1, right, temp);

            // 获取最后递归分解出来的两个元素的子数组，进行比较合并放置在正确的顺序
            merge(array, left, mid, right, temp);
            // 之后向上递归合并，即可得到正确的排列顺序
        }
    }

    /**
     * 合并方法
     * @param array 传入的需要排序的数组
     * @param left 左边有序序列的初始索引
     * @param mid 中间索引
     * @param right 右边的有序索引
     * @param temp 做中转的数组
     */
    public void merge(int[] array, int left, int mid, int right, int[] temp){
        // 左边有序序列的初始索引
        int i = left;
        // 右边有序序列的初始索引
        int j = mid + 1;
        // 指向temp数组的当前索引
        int t = 0;

        // 进行合并的时候 temp 数组中至少都有两个数据

        // 先把左右两边(有序)的数据按照规则填充到temp数组中
        // 直到两边的有序序列有一方处理完毕
        while (i <= mid && j <= right){
            // 如果左边的有序序列的当前元素 小于 右边有序序列的当前元素
            // 就将左边的当前拷贝到temp的当前位置，再将 t 和 i 后移
            if (array[i] <= array[j]){
                temp[t] = array[i];
                t ++;
                i ++;
            }
            // 反之将右边的当前元素拷贝到temp的当前位置
            else {
                temp[t] = array[j];
                t ++;
                j ++;
            }
        }

        // 把有剩余数据的一边的数据依次全部填充到temp
        // 左剩余
        while (i <= mid){
            temp[t] = array[i];
            t ++;
            i ++;
        }
        // 右剩余
        while (j <= right){
            temp[t] = array[j];
            t ++;
            j ++;
        }

        // 将temp数组中的元素重新拷贝到array中
        // 注意：在这里拷贝并不是每次都拷贝所有
        // 如这里是先进行左递归，所以合并顺序
        // 0  1 比较，合并
        // 0  1， 2  3 比较，合并
        t = 0;
        int tempLeft = left;
        while (tempLeft <= right){
            array[tempLeft] = temp[t];
            t ++;
            tempLeft ++;
        }
    }
}
